package com.taldh.algorithm.array;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ThreeSumSolution {

    public List<List<Integer>> threeSum(int[] nums) {
        // 时间复杂度 O(nlogn) 空间复杂度 O(n)
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int start = i + 1;
            int end = nums.length - 1;
            if(i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }
            while (start < end) {
                if (nums[i] + nums[start] + nums[end] == 0) {
                    ArrayList<Integer> oneResult = new ArrayList<>();
                    oneResult.add(nums[i]);
                    oneResult.add(nums[start]);
                    oneResult.add(nums[end]);
                    ans.add(oneResult);
                    start++;
                    end--;
                    while(start<end && nums[start]==nums[start-1]) {
                        start++;
                    }
                    while(start<end && nums[end]==nums[end+1]) {
                        end--;
                    }
                } else {
                    if (nums[i] + nums[start] + nums[end] < 0 ) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
        }
        return ans;
    }

    @Test
    public void test() {
        Assert.assertEquals("[[-1, -1, 2], [-1, 0, 1]]", threeSum(new int[]{-1,0,1,2,-1,-4}).toString());
    }

    @Test
    public void test2() {
        Assert.assertEquals("[[-2, 0, 2]]", threeSum(new int[]{-2,0,0,2,2}).toString());
    }

    @Test
    public void test3() {
        Assert.assertEquals("[[-2, 0, 2], [-2, 1, 1]]", threeSum(new int[]{-2,0,1,1,2}).toString());
    }

    @Test
    public void test4() {
        Assert.assertEquals("[[-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, 0, 2]]", threeSum(new int[]{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6}).toString());
    }
}